A tree k-spanner (or simply k-spanner) of a graph is a spanning subtree of in which the distance between every pair of vertices is at most times their distance in .